package pro.softzhang.algo.lc400;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.book.BLeetCode75;
import pro.softzhang.algo.flag.knowledge.KPrefixSum;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.HashMap;
import java.util.Map;

/**
 *
 */
@BLeetCode75
@XClassic
public class LC437_PathSumIII {
    public static void main(String[] args) {

    }

    /**
     * https://leetcode.cn/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     */
    @KPrefixSum
    @XOptimal
    static
    class LC437_Solution {
        public int pathSum(TreeNode root, int targetSum) {
            Map<Long, Long> map = new HashMap<>();
            map.put(0L, 1L);
            return doPathSum(root, targetSum, map, 0);
        }

        public int doPathSum(TreeNode root, long sum, Map<Long, Long> map, long path) {
            if(root == null) {
                return 0;
            }
            path += root.val;
            long count = map.getOrDefault(path - sum, 0L);
            map.put(path, map.getOrDefault(path, 0L) + 1);
            count += doPathSum(root.left, sum, map, path);
            count += doPathSum(root.right, sum, map, path);
            map.put(path, map.get(path) - 1);
            return (int)count;
        }
    }
}